package com.lihepeng.leecode.frequency.LinkedList;

import org.junit.Test;

/**
 *  判断链表是不是回文
 *
 */
public class Solution13 {
    /**
     * 使用快慢指针 来处理
     * 快指针每次执行两个
     * 慢指针执行一次
     * 等快指针执行到结尾的时候 将慢指针之后的数据翻转
     * 然后和原来的进行比较
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        ListNode fastNode = head;
        ListNode slowNode= head;
        while (fastNode!=null && fastNode.next != null) {
            fastNode = fastNode.next;
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        // 将slowNode 截断
        // 翻转链表
        ListNode listNode = revertNode(slowNode);
        ListNode headNode = head;
        while (listNode!=null ) {
            if (listNode.val!=headNode.val) {
                return false;
            }
            listNode = listNode.next;
            headNode = headNode.next;
        }
        return true;
    }
    private ListNode revertNode(ListNode listNode) {
        ListNode node = listNode;
        ListNode prev = null;
        while (node !=null) {
            ListNode nextNode = node.next;
            node.next = prev;
            prev = node;
            node = nextNode;
        }
        return prev;
    }
    @Test
    public void runTest() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        boolean pail = isPail(node1);
        System.out.println(pail);

    }
}
